`
https://leetcode.cn/problems/restore-ip-addresses/
`

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
  const res = []
  const track = []

  function backtrack(start) {
    // base case，走到叶子节点
    if (start === s.length && track.length === 4) {
      // 即整个 s 被成功分割为合法的四部分，记下答案
      res.push(track.join('.'));
      return;
    }

    for (let i = start; i < s.length; i++) {
      if (!isValid(s, start, i)) {
        // s[start..i] 不是合法的 ip 数字，不能分割
        continue;
      }
      if (track.length >= 4) {
        // 已经分解成 4 部分了，不能再分解了
        break;
      }
      track.push(s.substring(start, i + 1))
      backtrack(i + 1)
      track.pop()
    }
  }

  backtrack(0)
  return res
};

// 判断 s[start..end] 是否是一个合法的 ip 段
function isValid(s, start, end) {
  // 判断 s[
  let length = end - start + 1;
  if (length === 0 || length > 3) {
    return false;
  }
  if (length === 1) {
    // 如果只有一位数字，肯定是合法的
    return true;
  }
  if (s[start] === '0') {
    // 多于一位数字，但开头是 0，肯定不合法
    return false;
  }
  if (length <= 2) {
    // 排除了开头是 0 的情况，那么如果是两位数，怎么着都是合法的
    return true;
  }
  // 现在输入的一定是三位数
  if (parseInt(s.substring(start, start + length)) > 255) {
    // 不可能大于 255
    return false;
  } else {
    return true;
  }
}